%purpuses
Цели дипломной работы: разработать алгоритмы упрощения графа де Брюина.
Цели работы в проекте: предоставить для группы удобную, эффективную реализацию сжатого графа де Брюина и структур для хранения сопутствующей информации.
%%%%%%%%%%%%%%%%%%%%%

%input data
Как уже отмечалось, процесс выявления последовательности нуклеотидов разделен на два этапа: биологический (секвенирование) и алгоритмический (ассемблирование).
На выходе наиболее распространенные секвенаторы (генераторы ридов) генерируют файлы (обычно в формате FASTQ), содержащие полученные риды в виде строк пяти буквенного алфавита (помимо четырех базовых нуклеотидов, добавляется еще N, в случае, если секвенатор не смог определить нуклеотид с приемлимой степенью точности). Вместе с каждым ридом, в файле также содержится строка, кодирующая значения PHRED коэффициента для каждого нуклеотида. Это значение равно ...
Левые и правые части парных ридов записываются в 2 разных файла.

%from spisok thesis

%%%%%%%%%%%%%%%%% some intro
Певзнер с соавторами (\cite{PWMP}) предложил интересную метафору. Представьте, что большое количество экземпляров сегодняшнего номера газеты ``Times'' уложены в заминированный ящик. Ящик взрывается и каждая из газет рассыпается на маленькие конфети, содеращие по несколько слов. Задача: восстановить текст номера. При этом, с одной стороны, некоторая информация из каждой копии в отдельности могла быть уничтожена взрывом, а, с другой, так как газеты были идентичны, то разные кусочки бумаги будут накладываться друг на друга и содержать одни и те же участки текста.

Но хотя задача сборки генома по ридам генома и похожа на восстановление газеты по клочкам, на самом деле она значительно сложнее. И дело не только в том, что приходится иметь дело с миллиардом ридов (not simply because of the sheer scale of reconstructing
a genome from a billion reads). Во-первых, вспомним, что газета написана на некотором естественном языке, чьи правила могут подсказать нам взаимное расположение кусочков вне зависимости от того перекрываются они или нет. С другой стороны правила ``языка'' ДНК все еще в основном не известны биологам, так что практически невозможно определить даже примерное взаимное расположение двух неперекрывающихся ридов. Во-вторых, ``алфавит'' нуклеотидов содержит всего четыре буквы (A - adenin, T-..., G, C). Это сильно усложняет задачу, так как большое количество наблюдаемых нами наложений произошли совершенно случайно и не соответствуют одному участку исходной последовательности. В тертьих, ДНК содержит большое количество “conserved regions", это участки информации, повторенные в геноме большое количество раз с небольшими изменениями. Например, так называемый Alu, последовательность длины около $300$ нуклеотидов, встречается в человеческом геноме миллион раз, причем с отличием всего лишь в нескольких нуклеотидах (из-за вставок, удалений, замен).

Технология, позволившая бы "прочитать" полный геном нуклеотид за нуклеотидом остается неизвестной.
С другой стороны, мы можем интерпретировать короткие подпоследовательности ДНК, которые называются \textit{ридами}.
%сюда про секвенирование, ассемблирование??
Наиболее популярные (дешевые, быстрые) технологии производят риды длиной всего около 150 нуклеотидов (bp). Идея секвенирования состоит в продуцировании огромного количества ридов (множество раз покрывающих геном) из большого числа копий одного и того же генома и разгадывании гигантского пазла из перекрывающихся элементов. К примеру, для того, чтобы восстановить геном млекопитающего, необходимо несколько миллиардов ридов.

Таким образом, проблема секвенирования (??? что же секвенирование) сводится к генерации ридов (биологическая задача) и сборке (fragment assembly) (алгоритмическая задача).

Первые технологии генерации ридов появились в 1970-х, Walter Gilbert and Fred Sanger получили Нобелевскую премию за изобретение первой такой технологии. 

The problem of genome sequencing therefore reduces to read generation (a biological
problem) and fragment assembly (an algorithmic problem). Read generation has its own
long and tangled history that dates to the 1970s, when Walter Gilbert and Fred Sanger
won the Nobel prize for inventing the first read generation technology. 

%copypast!!!
In the early 1990s, modern DNA sequencing machines hit the market and the era of high-throughput DNA sequencing began. In 2000, a few hundred such machines working around the clock for over a year eventually generated enough reads to enable the fragment assembly of the human genome, which was completed within a few months by some of the world’s most powerful supercomputers.



%%%%%%%%%%%%%%%%%%%%
\section{Схема работы ассемблера}

\begin{itemize}
%где используется покрытие???
\item Коррекция ошибок 
\item Построение \db
\item Упрощение \db (на самом деле устранение ошибок с учетом структуры графа)
\item Разрешение коротких повторов на основе самих одиночных ридов
\item Разрешение повторов с использованием парных ридов
\item Выяснение кратности коротких циклов
\item Scaffolding
\item Этап консенсуса (consensus step)
\end{itemize}

\section{Графы де Брюина}
В 1946 году, голландский математик Николас де Брюин занимался проблемой поиска минимальной циклической подстроки, содержащей все возможные двоичные последовательности длины $l$ в качестве подстрок.

Он рассматривал особый класс графов, определяемый следующим образом. Рассмотрим $n-$буквенный алфавит и некоторое фиксированное число $l$. Сформируем множество всех возможных строк длины $l-1$ над этим алфавитом. Де Брейн рассмотрел граф $B(n, l)$, в котором в качестве вершин стоят все элементы построенного множества, а две вершины $v_1, v_2$ соединены направленным ребром тогда и только тогда, когда существует слово длины $l$, чьим префиксом является строка из $v_1$, а суффиксом строка из $v_2$. Граф содержит $n^{l-1}$ вершин. Нетрудно также заметить, что входящая и исходящая степень любой вершины этого графа равна $n$.

We would like to construct something like this graph from the set of our reads (we would see after why it is a good idea).

Для начала сделаем несколько упрощающих предположений, которые сделают дальнейшие шаги более естественными (естественно, затем мы от них откажемся)
\begin{itemize}
\item Геном, который мы восстанавливаем циклический (кстати, большое количество простых бактерий имеют именно такой).
\item Все риды имеют одну и ту же длину $l$.
\item Все возможные подстроки генома длины $l$ встречаются в множестве ридов.
\item Риды были сгенерированы без ошибок.
\end{itemize}

%copypast!!!
%Having generated all our reads, we will henceforth make three simplifying assumptions about the problem at hand in order to streamline our work:
%1. The genome we are reconstructing is cyclic.
%2. Every read has the same length l (a string of l nucleotides is called an “l-mer”).
%3. All possible substrings of length l occurring in our genome have been generated as reads.
%4. The reads have been generated without any errors.
%It turns out that we can relax each of these assumptions, but the resulting solution to fragment assembly winds up being far more technical than what is suitable for this text.

%%%%%%%%%%%%%


%%%%%%%%%About Hamiltonian approach

%In the early days of DNA sequencing, the following idea for fragment assembly was proposed. Construct a graph H by forming a vertex for every read (l-mer); we connect l mer R1 to l-mer R2 by a directed edge if the string formed by the final l − 1 characters of R1 (called the suffix of R1   matches the string formed by the first l − 1 characters of R2 (called the prefix of R2 ). For instance, in the case l = 5, we would connect GGCAT to GCATC by a directed edge, but not vice-versa. An example of such a graph H is provided in Figure 9a. Now, consider a cycle in H. It will begin with an l-mer R1 , and then proceed along a directed edge to a different l-mer R2 ; let us think of walking along this edge as beginning with R1 and tacking on the lone nonoverlapping character from R2 in order to form a “superstring” S of length l + 1. To continue our above example, if we walk from GGCAT to GCATC, then our superstring S will be GGCATC. Observe that the first l characters of S will be R1 , and the final l characters of S will be R2 . At each new vertex that we reach, we append one new character to S and notice that the final l characters of our superstring will represent the read at the present vertex. At the end of the cycle, our (cyclic) superstring S will therefore contain every l-mer that we reached along the way. Extending this reasoning, a Hamiltonian cycle in H, which travels to every vertex in H, must correspond to a superstring of nucleotides which contains every one of our l-mers.


Instead of assigning each read to a vertex, let us make the admittedly counterintuitive decision to assign each read to an edge. To this end, consider all prefixes and suffixes of all reads. Note that different reads may share suffixes and prefixes; for example, reads CAGC and CAGT of length 4 share the prefix CAG. We construct a graph E with each distinct prefix or suffix represented by a vertex; connect an (l − 1)-mer A to an (l − 1)-mer B via a directed edge if there exists a read whose prefix is A and whose suffix is B. %todo put fig 10 from pevzner final here

It's easy to see that this graph is the same as the de Bruijn graph earlier, but constructed not over the set of all strings of length $l$, but over the set of existing reads. Therefore $E$ is a subgraph of $B(4,l)$.

Here, then, is the critical question: What does a cycle in E represent? Once again,
imagine that you are an ant starting at some vertex of E and that you walk along a directed edge to another vertex. As with H, the result is the creation of a superstring S by tacking on the nonoverlapping characters from the second vertex to those of the first. However, in this case S is just the read representing the edge connecting the two vertices. Note that in Figure 10, we have labeled each edge with the appropriate 3-mer.
This process repeats itself as the ant walks through E; with each new edge, we ap-
pend one additional nucleotide to the superstring S, but we also gain one additional read.
Therefore, an Eulerian cycle in E will induce a (cyclic) superstring S that contains all our reads with maximum overlap, and so S is also a candidate DNA sequence. Yet in contrast to our above graph H, we have no computational troubles: by Euler’s Theorem, the ECP is easy to solve. Hence we have reduced fragment assembly to an easily solved computational
problem!

De Bruijn graphs. In 1946, the Dutch mathematician Nicolaas de Bruijn4 (see
Figure 14c) was interested in the problem of designing a circular superstring of minimal
length that contains all possible l-digit binary numbers as substrings. For example, the
circular string 00011101 contains all 3-digit binary numbers: 000, 001, 010, 011, 100, 101, 110, and 111. It is easy to see that 00011101 is a shortest such superstring, because it does not contain any “extra” digits, meaning that each 3-digit substring of 00011101 is the unique occurrence of one of the 3-digit binary numbers listed above. See Figure 11.

De Bruijn analyzed a specific class of graphs, defined as follows. Consider an alphabet
of n characters, as well as some fixed number l. Form all nl−1 possible “words” of length l−1, where a word is just a string of l−1 letters from our alphabet.5 De Bruijn constructed a graph B(n, l) (now known as the de Bruijn graph6 ) whose vertices are all nl−1 words of

There are nl−1 such words because there are n choices for the first letter, n choices for the second letter,
and so on. Since there are l − 1 letters to choose, we wind up with nl−1 total possibilities.

%%%%%%%about multiple edges
Figure 13: This more general version of the graph from Figure 10 allows for the case that
the same read occurs in more than one location in the genome. The good news is that this
generalization does not make the problem any more difficult to solve: an Eulerian cycle in
this graph will still correspond to a candidate DNA sequence.
mers. Furthermore, it can be demonstrated that E itself has an Eulerian cycle!
Read multiplicities and further complications. Imagine for a moment that our
genome is ATGCATGC. Then we will obtain four reads of length 3: ATG, TGC, GCA,
and CAT; however, this might lead us to reconstruct the genome as ATGC. The problem
is that each of these reads actually occurs twice in the original genome. Therefore, we
will need to adjust genome reconstruction so that we not only find all l-mers occurring as
reads, but we also find how many times each such l-mer occurs in the genome, called its
“l-mer multiplicity.” The good news is that we can still handle fragment assembly in the
case l-mer multiplicities are known.
We simply use the same graph E, except that if the multiplicity of an l-mer is k, we
will connect its prefix to its suffix via k edges (instead of just one). Continuing our ongoing
example from Figure 10, if during read generation we discover that each of the four 3-mers
TGC, GCG, CGT, and GTG has multiplicity 2, and that each of the six 3-mers ATG, TGG,
GGC, GCA, CAA, and AAT has multiplicity 1, we create the graph shown in Figure 13. In
general, it is easy to see that the graph resulting from adding multiplicity edges is Eulerian,
as both the indegree and outdegree of a vertex (represented by an (l − 1)-mer) equals the
number of times this (l − 1)-mer appears in the genome.

%todo important!
In practice, information about the exact multiplicities of (l − 1)-mers in the genome
may be difficult to obtain, even with modern sequencing technologies. However, computer
scientists have recently found a way to reconstruct the genome even when this information
is unavailable. Furthermore, DNA sequencing machines are prone to errors, our reads will
have varying lengths, and so on. However, with every variation to fragment assembly, it has
proven fruitful to apply some cousin of de Bruijn graphs in order to transform a question
involving Hamiltonian cycles into a different question about Eulerian cycles.



%In 1946, the Dutch mathematician Nicolaas de Bruijn4 (see Figure 14c) was interested in the problem of designing a circular superstring of minimal length that contains all possible l-digit binary numbers as substrings. For example, the circular string 00011101 contains all 3-digit binary numbers: 000, 001, 010, 011, 100, 101, 110, and 111. It is easy to see that 00011101 is a shortest such superstring, because it does not contain any “extra” digits, meaning that each 3-digit substring of 00011101 is the unique occurrence of one of the 3-digit binary numbers listed above.

%The crucial property shared by all de Bruijn graphs is that every one of them will always contain an Eulerian cycle. For example, in Figure 12 we can see that there are two edges entering every vertex and two edges leaving every vertex of B(2, 4), implying that it has an Eulerian cycle. To see why the same is true for any de Bruijn graph B(n, l), consider a vertex w corresponding to a word of length l − 1. There exist n words of length l whose prefix is w (each such word is obtained by adding one of n letters to the end of w) and thus the outdegree of each vertex in B(n, l) is n. Similarly, there exist n words of length l whose suffix is w (each such word is obtained by adding one of n letters to the beginning of w) and thus the indegree of each vertex in B(n, l) is also n. Hence every vertex of B(n, l) has indegree and outdegree both equal to n, and so Euler’s Theorem implies that B(n, l) must have an Eulerian cycle. The biological connection arises when we realize that our graph E above will be contained in the de Bruijn graph B(4, l), because whereas the vertices of E are all (l − 1)-mers occurring as prefixes or suffixes of our reads, the vertices of B(4, l) are all possible (l − 1)-mers. Furthermore, it can be demonstrated that E itself has an Eulerian cycle!
